package code;


//题目链接：https://leetcode.cn/problems/count-unguarded-cells-in-the-grid/description/?envType=daily-question&envId=2025-11-02
public class CountUnguarded {
	// 延与扩展
	class Solution {
	    public static int[] dx={1,-1,0,0};
	    public static int[] dy={0,0,1,-1};

	    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
	        char[][] grid=new char[m][n];
	        boolean[] row=new boolean[m];
	        boolean[] col=new boolean[n];

	        //标记G和W
	        for(int i=0;i<guards.length;i++){
	            grid[guards[i][0]][guards[i][1]]='*';
	        }
	        for(int i=0;i<walls.length;i++){
	            grid[walls[i][0]][walls[i][1]]='*';
	        }
	        int ret=0;
	        
	        //枚举每个G点能保卫的点
	        for(int k=0;k<4;k++){
	            for(int[] em:guards){
	                int nx=em[0],ny=em[1];
	                int x=nx+dx[k],y=ny+dy[k];
	                while(x>=0&&y>=0&&x<m&&y<n&&grid[x][y]!='*'){
	                    grid[x][y]='.';
	                    x+=dx[k];
	                    y+=dy[k];
	                }
	            }
	        }
	        
	        //统计未被保卫的点
	        for(int i=0;i<m;i++){
	            for(int j=0;j<n;j++){
	                if(grid[i][j]==0) ret++;
	            }
	        }
	        return ret;
	    }
	}

}
